"""
题目描述：给你二叉树的根节点 root ，返回其节点值的层序遍历（即逐层地，从左到右访问所有节点）。
"""

from collections import deque
# 定义二叉树节点
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def levelOrder(root: TreeNode):
    # 处理空树情况
    if not root:
        return []

    # 结果列表
    result = []
    # 队列用于层序遍历，初始放入根节点
    q = deque([root])

    # 当队列不为空时循环
    while q:
        # 当前层的节点数量
        level_size = len(q)
        # 存储当前层的节点值
        current_level = []

        # 遍历当前层的所有节点
        for _ in range(level_size):
            # 弹出队首节点
            node = q.popleft()
            # 将节点值加入当前层列表
            current_level.append(node.val)

            # 如果有左子节点，加入队列
            if node.left:
                q.append(node.left)
            # 如果有右子节点，加入队列
            if node.right:
                q.append(node.right)

        # 将当前层的节点值加入结果列表
        result.append(current_level)

    return result


# 测试示例
# 构建二叉树:
#     3
#    / \
#   9  20
#     /  \
#    15   7
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(levelOrder(root))  # [[3], [9, 20], [15, 7]]